package org.lql.algo.codecrush.hot100.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 22:13
 * @description: 39. 组合总和 <a href="https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class CombinationSum {

	List<Integer> chosen;
	List<List<Integer>> ans;
	int[] candidates;

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		this.chosen = new ArrayList<>();
		this.ans = new ArrayList<>();
		this.candidates = candidates;
		combine(0, target);
		return ans;
	}

	public void combine(int pos, int target) {
		// 边界
		if (target == 0) {
			ans.add(new ArrayList<>(chosen));
			return;
		}
		for (int i = pos; i < candidates.length; i++) {
			// 剪枝：如果候选数大于剩余目标，则跳过
			if (candidates[i] > target) {
				continue;
			}
			chosen.add(candidates[i]);
			combine(i, target - candidates[i]);
			chosen.remove(chosen.size() - 1);
		}
	}

	public static void main(String[] args) {
		CombinationSum combinationSum = new CombinationSum();
		int[] candidates = {2, 3, 6, 7};
		int target = 7;
		System.out.println(combinationSum.combinationSum(candidates, target));
	}
}
